home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / agrep / asearch.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  11KB  |  314 lines
  1. /* Copyright (c) 1991 Sun Wu and Udi Manber.  All Rights Reserved. */
  2. #include "agrep.h"
  3.  
  4. extern unsigned Init1, Init[], Mask[], endposition, D_endpos, AND, NO_ERR_MASK;
  5. extern int DELIMITER, FILENAMEONLY, INVERSE;
  6. extern CHAR CurrentFileName[];
  7. extern int I, num_of_matched, TRUNCATE;
  8.  
  9. asearch(old_D_pat, text, D)
  10. CHAR old_D_pat[]; int text; register unsigned D;
  11. {
  12.   register unsigned i, c, r1, r2, CMask, r_NO_ERR, r_Init1; 
  13.   register unsigned A0, B0, A1, B1, endpos;
  14.   unsigned A2, B2, A3, B3, A4, B4;
  15.   unsigned A[MaxError+1], B[MaxError+1];
  16.   unsigned D_Mask;
  17.   unsigned end;
  18.   int D_length, FIRSTROUND, ResidueSize, lasti, l, k, buffer_end, j=0;
  19.   int printout_end;
  20.   CHAR buffer[2*Max_record+1];
  21.      
  22.   if (I == 0) Init1 = 037777777777;
  23.   if(D > 4) {
  24.          asearch0(old_D_pat, text, D); 
  25.          return;  }
  26.   D_length = strlen(old_D_pat);
  27.   buffer[Max_record-1] = '\n';
  28.   D_Mask = D_endpos;
  29.   for ( i=1; i<D_length; i++) D_Mask = (D_Mask<<1) | D_Mask;
  30.   D_Mask = ~D_Mask;
  31.  
  32.   r_Init1 = Init1; /* put Init1 in register */
  33.   r_NO_ERR = NO_ERR_MASK; /* put NO_ERR_MASK in register */
  34.   endpos = D_endpos;    
  35.   FIRSTROUND = ON;
  36.   A0 = B0 = A1 = B1 = A2 = B2 = A3 = B3 = A4 = B4 = Init[0];
  37.   for(k=0; k<=D; k++) A[k] = B[k] = Init[0];
  38.   lasti = Max_record;
  39.  
  40.   while ((l = fill_buf(text, buffer + Max_record, Max_record)) > 0)
  41.   { i = Max_record; end = Max_record + l ;
  42.     if (FIRSTROUND) { 
  43.         i = Max_record - 1;
  44.     if(DELIMITER) {
  45.         for(k=0; k<D_length; k++) {
  46.                     if(old_D_pat[k] != buffer[Max_record+k])                         break;
  47.         }
  48.         if(k>=D_length) j--;
  49.     }
  50.         FIRSTROUND = OFF; }
  51.     if (l < BlockSize) {
  52.         strncpy(buffer+end, old_D_pat, D_length);
  53.         buffer[end+D_length] = '\0';
  54.         end = end + D_length; }
  55.     while (i < end )
  56.     {
  57.         c = buffer[i];
  58.         CMask = Mask[c];
  59.               r1 = r_Init1 & B0;
  60.               A0 = ((B0 >>1 ) & CMask) | r1;
  61.               r1 = r_Init1 & B1;
  62.               r2 =  B0 | (((A0 | B0) >> 1) & r_NO_ERR); 
  63.               A1 = ((B1 >>1 ) & CMask) | r2 | r1 ;  
  64.                      if(D == 1) goto Nextchar;
  65.               r1 = r_Init1 & B2;
  66.               r2 =  B1 | (((A1 | B1) >> 1) & r_NO_ERR); 
  67.               A2 = ((B2 >>1 ) & CMask) | r2 | r1 ;  
  68.                      if(D == 2) goto Nextchar;
  69.               r1 = r_Init1 & B3;
  70.               r2 =  B2 | (((A2 | B2) >> 1) & r_NO_ERR); 
  71.               A3 = ((B3 >>1 ) & CMask) | r2 | r1 ;  
  72.                      if(D == 3) goto Nextchar;
  73.               r1 = r_Init1 & B4;
  74.               r2 =  B3 | (((A3 | B3) >> 1) & r_NO_ERR); 
  75.               A4 = ((B4 >>1 ) & CMask) | r2 | r1 ;  
  76.                      if(D == 4) goto Nextchar;
  77. Nextchar: i=i+1;
  78.         if(A0 & endpos) {
  79.            j++;  r1 = A0;
  80.            if ( D == 1) r1 = A1;
  81.            if ( D == 2) r1 = A2;
  82.            if ( D == 3) r1 = A3;
  83.            if ( D == 4) r1 = A4;
  84.            if(((AND == 1) && ((r1 & endposition) == endposition)) ||                           ((AND == 0) && (r1 & endposition)) ^ INVERSE )
  85.                  {    
  86.                       if(FILENAMEONLY) {
  87.                          num_of_matched++;
  88.                          printf("%s\n", CurrentFileName);
  89.                          return;  }
  90.                       printout_end = i - D_length - 1;           
  91.                       if(!(lasti >= Max_record + l - 1))
  92.                          output(buffer, lasti, printout_end, j);
  93.                  }
  94.            lasti = i - D_length; /* point to starting position of D_pat */
  95.            TRUNCATE = OFF;
  96.            for(k=0; k<= D; k++) {
  97.               B[k] = Init[0];
  98.            }
  99.            r1 = B[0] & Init1;
  100.            A[0] = (((B[0]>>1) & CMask) | r1) & D_Mask;
  101.            for(k=1; k<= D; k++) {
  102.               r1 = Init1 & B[k];
  103.               r2 = B[k-1] | (((A[k-1] | B[k-1])>>1)&r_NO_ERR);
  104.               A[k] = (((B[k]>>1)&CMask) | r1 | r2) ;
  105.            }
  106.            A0 = A[0]; B0 = B[0]; A1 = A[1]; B1 = B[1]; A2 = A[2]; B2 = B[2];
  107.            A3 = A[3]; B3 = B[3]; A4 = A[4]; B4 = B[4];
  108.         }
  109.         c = buffer[i];
  110.         CMask = Mask[c];
  111.               r1 = r_Init1 & A0;
  112.               B0 = ((A0 >> 1 ) & CMask) | r1;
  113. #ifdef DEBUG
  114.     printf("Mask = %o, B0 = %o\n", CMask, B0);
  115. #endif
  116.               r1 = r_Init1 & A1;
  117.               r2 =  A0 | (((A0 | B0) >> 1) & r_NO_ERR); 
  118.               B1 = ((A1 >>1 ) & CMask) | r2 | r1 ;  
  119.                      if(D == 1) goto Nextchar1;
  120.               r1 = r_Init1 & A2;
  121.               r2 =  A1 | (((A1 | B1) >> 1) & r_NO_ERR); 
  122.               B2 = ((A2 >>1 ) & CMask) | r2 | r1 ;  
  123.                      if(D == 2) goto Nextchar1;
  124.               r1 = r_Init1 & A3;
  125.               r2 =  A2 | (((A2 | B2) >> 1) & r_NO_ERR); 
  126.               B3 = ((A3 >>1 ) & CMask) | r2 | r1 ;  
  127.                      if(D == 3) goto Nextchar1;
  128.               r1 = r_Init1 & A4;
  129.               r2 =  A3 | (((A3 | B3) >> 1) & r_NO_ERR); 
  130.               B4 = ((A4 >>1 ) & CMask) | r2 | r1 ;  
  131.                      if(D == 4) goto Nextchar1;
  132. Nextchar1: i=i+1;
  133.         if(B0 & endpos) {
  134.            j++;  r1 = B0;
  135.            if ( D == 1) r1 = B1;
  136.            if ( D == 2) r1 = B2;
  137.            if ( D == 3) r1 = B3;
  138.            if ( D == 4) r1 = B4;
  139.            if(((AND == 1) && ((r1 & endposition) == endposition)) ||                           ((AND == 0) && (r1 & endposition)) ^ INVERSE )
  140.                  { 
  141.                     if(FILENAMEONLY) {
  142.                        num_of_matched++;
  143.                        printf("%s\n", CurrentFileName);
  144.                        return; }
  145.                     printout_end = i - D_length -1 ; 
  146.                     if(!(lasti >= Max_record + l - 1))
  147.                        output(buffer, lasti, printout_end, j);
  148.                  }
  149.            lasti = i - D_length ;
  150.            TRUNCATE = OFF;
  151.            for(k=0; k<= D; k++) {
  152.               A[k] = Init[0];
  153.            }
  154.            r1 = A[0] & Init1; 
  155.            B[0] = (((A[0]>>1)&CMask) | r1) & D_Mask;
  156.            for(k=1; k<= D; k++) {
  157.               r1 = Init1 & A[k];
  158.               r2 = A[k-1] | (((A[k-1] | B[k-1])>>1)&r_NO_ERR);
  159.               B[k] = (((A[k]>>1)&CMask) | r1 | r2) ;
  160.            }
  161.            A0 = A[0]; B0 = B[0]; A1 = A[1]; B1 = B[1]; A2 = A[2]; B2 = B[2];
  162.            A3 = A[3]; B3 = B[3]; A4 = A[4]; B4 = B[4];
  163.         }
  164.     }
  165.     if(l < BlockSize) {
  166.            lasti = Max_record ;
  167.     }
  168.     else {
  169.        ResidueSize = Max_record + l - lasti;
  170.        if(ResidueSize > Max_record) {
  171.           ResidueSize = Max_record;
  172.           TRUNCATE = ON;         }
  173.        strncpy(buffer+Max_record-ResidueSize, buffer+lasti, ResidueSize);
  174.        lasti = Max_record - ResidueSize;
  175.        if(lasti == 0)     lasti = 1; 
  176.     }
  177.   }
  178.   return;
  179. }
  180.  
  181. asearch0(old_D_pat, text, D)
  182. CHAR old_D_pat[]; int text; register unsigned D;
  183. {
  184.   register unsigned i, c, r1, r2, r3, CMask, r_NO_ERR, r_Init1,  end, endpos; 
  185.   unsigned A[MaxError+2], B[MaxError+2];
  186.   unsigned D_Mask;
  187.   int D_length, FIRSTROUND, ResidueSize, lasti, l, k, buffer_end, j=0;
  188.   int printout_end;
  189.   CHAR buffer[BlockSize+Max_record+1];
  190.   
  191.   D_length = strlen(old_D_pat);
  192.   buffer[Max_record-1] = '\n';
  193.   D_Mask = D_endpos;
  194.   for ( i=1; i<D_length; i++) D_Mask = (D_Mask<<1) | D_Mask;
  195.   D_Mask = ~D_Mask;
  196.  
  197.   r_Init1 = Init1; /* put Init1 in register */
  198.   r_NO_ERR = NO_ERR_MASK; /* put NO_ERR_MASK in register */
  199.   endpos = D_endpos;    
  200.   FIRSTROUND = ON;
  201.   for(k=0; k<=D; k++) A[k] = B[k] = Init[0];
  202.   lasti = Max_record;
  203.  
  204.   while ((l = fill_buf(text, buffer + Max_record, Max_record)) > 0)
  205.   { i = Max_record; end = Max_record + l ;
  206.     if (FIRSTROUND) { 
  207.         i = Max_record - 1;
  208.         FIRSTROUND = OFF; }
  209.     if (l < BlockSize) {
  210.         strncpy(buffer+end, old_D_pat, D_length);
  211.         buffer[end+D_length] = '\0';
  212.         end = end + D_length; }
  213.     while (i < end )
  214.     {
  215.         c = buffer[i++];
  216.         CMask = Mask[c];
  217.               r1 = B[0] & r_Init1;
  218.               A[0] = (((B[0] >> 1)) & CMask | r1 ) ;
  219.               for(k=1; k<=D; k++) {
  220.                      r1 = r_Init1 & B[k];
  221.                      r2 = B[k-1] | (((A[k-1]|B[k-1])>>1) & r_NO_ERR);
  222.                      A[k] = ((B[k] >> 1) & CMask) | r2 | r1;
  223.               }
  224.         if(A[0] & endpos) {
  225.            j++;  
  226.            r1 = A[D];
  227.            if(((AND == 1) && ((r1 & endposition) == endposition)) ||                           ((AND == 0) && (r1 & endposition)) ^ INVERSE )
  228.                  {    
  229.                       if(FILENAMEONLY) {
  230.                          num_of_matched++;
  231.                          printf("%s\n", CurrentFileName);
  232.                          return;  }
  233.                       printout_end = i - D_length - 1;           
  234.                       if(!(lasti >= Max_record + l - 1))
  235.                          output(buffer, lasti, printout_end, j);
  236.                  }
  237.            lasti = i - D_length; /* point to starting position of D_pat */
  238.            for(k=0; k<= D; k++) {
  239.               B[k] = Init[0];
  240.            }
  241.            r1 = B[0] & r_Init1;
  242.            A[0] = (((B[0]>>1) & CMask) | r1) & D_Mask;
  243.            for(k=1; k<= D; k++) {
  244.               r1 = Init1 & B[k];
  245.               r2 = B[k-1] | (((A[k-1] | B[k-1])>>1)&r_NO_ERR);
  246.               A[k] = (((B[k]>>1)&CMask) | r1 | r2) ;
  247.            }
  248.         }
  249.         c = buffer[i++];
  250.         CMask = Mask[c];
  251.               r1   = r_Init1 & A[0];
  252.               B[0] = ((A[0] >> 1 ) & CMask) | r1;
  253.               for(k=1; k<=D; k++) {
  254.                      r1 = r_Init1 & A[k];
  255.                      r2 = A[k-1] | (((A[k-1]|B[k-1])>>1) & r_NO_ERR);
  256.                      B[k] = ((A[k] >> 1) & CMask) | r2 | r1;
  257.               }
  258.         if(B[0] & endpos) {
  259.            j++;  
  260.            r1 = B[D];
  261.            if(((AND == 1) && ((r1 & endposition) == endposition)) ||                           ((AND == 0) && (r1 & endposition)) ^ INVERSE )
  262.                  { 
  263.                     if(FILENAMEONLY) {
  264.                        num_of_matched++;
  265.                        printf("%s\n", CurrentFileName);
  266.                        return; }
  267.                     printout_end = i - D_length -1 ; 
  268.                     if(!(lasti >= Max_record + l - 1))
  269.                        output(buffer, lasti, printout_end, j);
  270.                  }
  271.            lasti = i - D_length ;
  272.            for(k=0; k<= D; k++) {
  273.               A[k] = Init[0];
  274.            }
  275.            r1 = A[0] & r_Init1; 
  276.            B[0] = (((A[0]>>1)&CMask) | r1) & D_Mask;
  277.            for(k=1; k<= D; k++) {
  278.               r1 = r_Init1 & A[k];
  279.               r2 = A[k-1] | (((A[k-1] | B[k-1])>>1)&r_NO_ERR);
  280.               B[k] = (((A[k]>>1)&CMask) | r1 | r2) ;
  281.            }
  282.         }
  283.     }
  284.     if(l < BlockSize) {
  285.            lasti = Max_record;
  286.     }
  287.     else {
  288.        ResidueSize = Max_record + l - lasti;
  289.        if(ResidueSize > Max_record) {
  290.           ResidueSize = Max_record;
  291.           TRUNCATE = ON;         }
  292.        strncpy(buffer+Max_record-ResidueSize, buffer+lasti, ResidueSize);
  293.        lasti = Max_record - ResidueSize;
  294.        if(lasti == 0)     lasti = 1; 
  295.     }
  296.   }
  297.   return;
  298. }
  299.  
  300.  
  301. /*
  302. fill_buf(fd, buf, record_size)
  303. int fd, record_size; unsigned char *buf;
  304. {
  305. int num_read=1;
  306. int total_read=0;
  307.     while(total_read < record_size && num_read > 0) {
  308.         num_read = read(fd, buf+total_read, 4096);
  309.         total_read = total_read + num_read;
  310.     }
  311.     return(total_read);
  312. }
  313. */
  314.